# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/6/1 17:57
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : subset_sum.py
@Version     : Version 1.0.0
@Description : TODO
@Created By  : PyCharm
"""


def subset_sum(lst, target):
    for i in range(1, 2 ** len(lst)):
        pick = list(mask(lst, bin(i)[2:]))
        if sum(pick) == target:
            yield pick


def mask(lst, m):
    m = m.zfill(len(lst))  # 按照lst的位数扩展m
    return map(lambda x: x[0], filter(lambda x: x[1] != '0', zip(lst, m)))


if __name__ == '__main__':
    ls = [-7, -3, -2, 5, 8]
    print(subset_sum(ls, 0).__next__())
